package com.su.ou.yang;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;

public class Test4 {
    static class TreeNode{
        int val=0;
        TreeNode left=null;
        TreeNode right=null;

        public TreeNode(int i) {
           this.val=i;
        }
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2= new TreeNode(2);
        TreeNode node3= new TreeNode(3);
        TreeNode node4= new TreeNode(4);
        TreeNode node5= new TreeNode(3);
        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node5;

        node2.right=node4;
        ArrayList<ArrayList<Integer>> res = solve(root, 4);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }
    public  static ArrayList<ArrayList<Integer>> solve(TreeNode root,int sum){
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<>();
        dfs(root,sum,res,list);
        return res;

    }

    private static void dfs(TreeNode root, int sum, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
      if(root==null){
          return;
      }
      list.add(root.val);
      if(root.left==null&&root.right==null){
          if(sum==root.val){
              res.add(new ArrayList<Integer>(list));
          }
          list.remove(list.size()-1);
          return;
      }
      dfs(root.left, sum-root.val, res, list);
      dfs(root.right,sum-root.val,res,list);
      list.remove(list.size()-1);


    }
}
